package treesNgraphs;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.LinkedBlockingDeque;

/**
 *
 * Created by Tzachi on 21/10/2014.
 *
 * OrigamiLogic first technical interview
 */
public class PrintAllGraphPaths {
    public static class Node {
        private final String value;
        private final List<Node> children = new LinkedList<>();
        public Node(String value) {
            this.value = value;
        }
        public String getValue() {
            return value;
        }
        public List<Node> getChildren() {
            return children;
        }
    }

    public static void printAllTreePaths(Node node, Deque<String> path) {
        if (node.children.isEmpty()) {
            path.add(node.getValue());
            printPath(path);
        } else {
            path.add(node.getValue());
            for (Node child : node.getChildren()) {
                printAllTreePaths(child, path);
                path.pollLast();
            }
        }
    }

    public static void printAllTreePaths2(Node node, List<String> path) {
        if (node.children.isEmpty()) {
            path.add(node.getValue());
            // the conversion is from laziness... :)
            printPath(new LinkedBlockingDeque<>(path));
        } else {
            path.add(node.getValue());
            for (Node child : node.getChildren()) {
                printAllTreePaths2(child, path);
                path.remove(child.getValue());
            }
        }
    }

    private static void printPath(Deque<String> path) {
        for (String s : path) {
            System.out.print(s + " ---> ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node root = new Node("1");
        Node node2 = new Node("2");
        node2.getChildren().add(new Node("5"));
        node2.getChildren().add(new Node("7"));
        root.getChildren().add(node2);
        root.getChildren().add(new Node("3"));
        printAllTreePaths(root, new LinkedList<>());
        System.out.println("===============");
        printAllTreePaths2(root, new LinkedList<>());
    }
}